Định nghĩa

Định lý Euler (Còn gọi là tiêu chuẩn Euler) khẳng định với mọi số nguyên tố p và mọi số a:

a p − 1 2 ≡ ( a p ) ( mod p ) {\displaystyle a^{\frac {p-1}{2}}\equiv \left({\frac {a}{p}}\right){\pmod {p}}} .

trong đó ( a p ) {\displaystyle \left({\frac {a}{p}}\right)} là ký hiệu Legendre.Ký hiệu Legendre chỉ được định nghĩa cho số nguyên tố p. Khi mở rộng ký hiệu Legendre cho số tự nhiên lẻ n và số tự nhiên a ta có ký hiệu Jacobi được ký hiệu giống như ký hiệu Legendre:

( a n ) {\displaystyle \left({\frac {a}{n}}\right)} .

Số tự nhiên lẻ n thoả mãn đồng dư thức tương tự định lý Euler:

a n − 1 2 ≡ ( a n ) ( mod n ) {\displaystyle a^{\frac {n-1}{2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}} .

với a nào đó được gọi là số nguyên tố xác suất Euler-Jacobi cơ sở a. Nếu n là hợp số thoả mãn đồng dư thức trên nó được gọi là số giả nguyên tố Euler-Jacobi cơ sở a.

Các kết quả

1. Mọi số giả nguyên tố Euler-Jacobi cơ sở a đều là số giả nguyên tố Euler cơ sở a.
2. Mọi số giả nguyên tố Fermat mạnh cơ sở a đều là số giả nguyên tố Euler-Jacobi.
3. Mọi số giả nguyên tố Euler-Jacobi cơ sở a thoả mãn một trong hai điều kiện sau là số giả nguyên tố mạnh cơ sở a:
   1. n ≡ 3 ( mod 4 ) {\displaystyle n\equiv 3{\pmod {4}}} ;
   2. Ký hiệu Jacobi ( a n ) = − 1 {\displaystyle \left({\frac {a}{n}}\right)=-1}

• Các số nguyên tố xác suất Euler-Jacobi được sử dụng trong kiểm tra Solovay-Strassen để kiểm tra tính nguyên tố theo xác suất.